package main

//#link: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
import (
	. "whoops/leetcode/common"
)

func main() {

}

//给定一个二叉树的根节点 root ，返回它的 中序 遍历。
func inorderTraversal(root *TreeNode) []int {
	result := make([]int, 0)
	stack := new(Stack)
	for len(stack.Nums) > 0 || root != nil {
		if root != nil {
			stack.push(root)
			root = root.Left
		} else {
			root = stack.pop()
			result = append(result, root.Val)
			root = root.Right
		}
	}
	return result
}

type Stack struct {
	Nums []*TreeNode
}

func (s *Stack) push(node *TreeNode) {
	if len(s.Nums) == 0 {
		s.Nums = make([]*TreeNode, 0)
	}
	s.Nums = append(s.Nums, node)
}

func (s *Stack) pop() *TreeNode {
	sLen := len(s.Nums)
	node := s.Nums[sLen-1]
	s.Nums = s.Nums[:sLen-1]
	return node
}
